/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/min-stack
   @Language: C++
   @Datetime: 16-02-09 08:17
   */

// Method 1, Time O(n), Space O(n)
class MinStack {
	stack<int> data;
	stack<int> mins;
public:
	MinStack() {
		// do intialization if necessary
	}

	/*
	 * @param number: An integer
	 * @return: nothing
	 */
	void push(int number) {
		// write your code here
		data.push(number);
		if(mins.size()<1 || (mins.size() && mins.top()>number)) mins.push(number);
		else mins.push(mins.top());
	}

	/*
	 * @return: An integer
	 */
	int pop() {
		// write your code here
		if(data.size()<1) return 0;
		int number=data.top();
		data.pop();
		mins.pop();
		return number;
	}

	/*
	 * @return: An integer
	 */
	int min() {
		// write your code here
		if(mins.size()<1) return 0;
		return mins.top();
	}
};


// Method 2, Time O(n), Space O(1)
class MinStack {
	stack<int> diff;
	int min_ele;
public:
	MinStack() {
		// do intialization if necessary
	}

	/*
	 * @param number: An integer
	 * @return: nothing
	 */
	void push(int number) {
		// write your code here
		if(diff.size()<1) min_ele=number;
		diff.push(number-min_ele);
		min_ele=min_ele<number?min_ele:number;
	}

	/*
	 * @return: An integer
	 */
	int pop() {
		// write your code here
		if(diff.size()<1) return 0;
		int d=diff.top();
		diff.pop();
		if(d<0) min_ele-=d;
		return min_ele+d;
	}

	/*
	 * @return: An integer
	 */
	int min() {
		// write your code here
		if(diff.size()<1) return 0;
		return min_ele;
	}
};

